package DataStructure.tree;

//左倾红黑树
public class RedBlackTree<K extends Comparable<K>,V> {
    private Node<K,V> root;
    private int size;

    private static class Node<K extends Comparable<K>,V>{
        private K key;
        private V value;
        private Node<K,V> left;
        private Node<K,V> right;
        private boolean red;//是否为红节点
        public Node(K key, V value, Node<K,V> left, Node<K,V> right,boolean red) {
            this.key=key;
            this.value=value;
            this.left=left;
            this.right=right;
            this.red=red;
        }
    }
    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return size==0;
    }
    private boolean isRed(Node<K,V> n){
        return n!=null&&n.red;
    }
    //添加节点
    public void put(K key,V value){
        root=put(root,key,value);
        root.red=false;
    }
    private Node<K,V> put(Node<K,V> n,K key,V value){
        if(n==null){
            size++;
            return new Node<>(key,value,null,null,true);//插入红色节点不会影响子节点到根的黑色路径
        }
        int cmp=key.compareTo(n.key);
        if(cmp>0)
            n.right=put(n.right,key,value);
        else if(cmp<0)
            n.left=put(n.left,key,value);
        else
            n.value=value;//存在key,直接修改
        //只有当插入节点的父节点为红时需要调整
        if(isRed(n.left)&&isRed(n.right))
            reverseColor(n);
        if(isRed(n.right)&&!isRed(n.left))
            n=leftRotate(n);
        if(isRed(n.left)&&isRed(n.left.left))
            n=rightRotate(n);
        return n;
    }
    //查找节点
    public V get(K key){
        return get(root,key);
    }
    private V get(Node<K,V> n, K key){
        if(n==null)//不存在
            return null;
        int tmp=key.compareTo(n.key);
        if(tmp>0)
            return get(n.right,key);
        else if(tmp<0)
            return get(n.left,key);
        else
            return n.value;//存在
    }
    //删除节点 todo
    public Node<K,V> remove(K key){
        return remove(root,key);
    }
    private Node<K,V> remove(Node<K,V> n, K key) {
        if (n == null)//不存在
            return null;
        //查找key对应节点
        int tmp = key.compareTo(n.key);
        if (tmp > 0) {
            n.right = remove(n.right, key);
        } else if (tmp < 0) {
            n.left = remove(n.left, key);
        } else {
            size--;
            if (n.right == null)
                n = n.left;
            else if (n.left == null)
                n = n.right;
            else {
                //查找右子树最小节点
                Node<K,V> min = min(n.right);
                //替换当前节点
                n.key = min.key;
                n.value = min.value;
                n.right = remove(n.right, min.key);//删除min
            }
        }
        if (n == null) return null;
        return null;

    }
    //获取最小节点
    private Node<K,V> min(Node<K,V> n){
        if(n.left!=null)
            return min(n.left);
        else
            return n;
    }
    //是否包含节点
    public boolean contains(K key){
        return get(key)!=null;
    }
    private Node<K,V> rightRotate(Node<K,V> n) {
        Node<K,V> ans=n.left;
        n.left=ans.right;
        ans.right=n;
        ans.red=n.red;
        n.red=true;
        return ans;
    }
    private Node<K,V> leftRotate(Node<K,V> n) {
        Node<K,V> ans=n.right;
        n.right=ans.left;
        ans.left=n;
        ans.red=n.red;
        n.red=true;
        return ans;
    }
    private void reverseColor(Node<K,V> n){
        n.red=true;
        n.left.red=false;
        n.right.red=false;
    }
}
